/**
 * 41. First Missing Positive 缺失的第一个正数
 * https://leetcode.com/problems/first-missing-positive/description/
 */
class FirstMissingPositive {
    /**
     * 方法：使用原地哈希法找到缺失的第一个正整数
     * 
     * Args:
     *     nums: int[] - 输入整数数组
     * 
     * Returns:
     *     int - 缺失的第一个正整数
     * 
     * Time: O(n) - 每个元素最多被交换一次
     * Space: O(1) - 只使用了常数个额外空间
     */
    public int firstMissingPositive(int[] nums) {
       int n = nums.length;
       for(int i = 0; i < n; i++){
          while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
              int j = nums[i] - 1;
              int tmp = nums[i];
              nums[i] = nums[j];
              nums[j] = tmp;
            
          }
       }
       for(int i = 0; i< n; i++){
           if(nums[i] != i +1){
               return i + 1;
           }
       }
       return n + 1;
    }
}